public class magic_cube{
    public static int total = 0;

    public static void main(String[] args) {
        
        int[][] matrix = { { 1, 3, 0, 0, 7, 0, 0, 0, 0 }, { 6, 0, 0, 1, 9, 5, 0, 0, 0 }, { 0, 9, 8, 0, 0, 0, 0, 6, 0 },
                { 8, 0, 0, 0, 6, 0, 0, 0, 3 }, {
                        4, 0, 0, 8, 0, 3, 0, 0, 1 },
                { 7, 0, 0, 0, 2, 0, 0, 0, 6 }, { 0, 6, 0, 0, 0, 0, 2, 8, 0 }, { 0, 0, 0, 4, 1, 9, 0, 0, 5 },
                { 0, 0, 0, 0, 8, 0, 0, 7, 9 } };

        int[][][] visit = new int[9][9][10];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                for (int m = 0; m < 10; m++) {
                    visit[i][j][m] = 0;
                }
            }
        }
        getisempty(matrix, visit);
        addnumber(matrix, visit);

        back(matrix, visit);
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                System.out.printf("%d ", matrix[i][j]);
            }
            System.out.println("\n");
        }
    }

    public static void qiu(int t, int sum, int[] a, int s, int n) {
        if (sum > 0) {
            if (n == s)
                return;
            for (int i = n; i <= sum; i++) {
                a[t] = i;
                sum -= i;
                if (sum == 0 && i != 10) {
                    total++;

                } else
                    qiu(t + 1, sum, a, s, i + 1);

                a[t] = 0;
                sum += i;
            }
        }

    }

    public static void printm(int[] a, int s) {
        System.out.printf("%d=", s);
        for (int i = 0; i < a.length; i++) {
            if (a[i] != 0) {
                s -= a[i];
                if (s != 0)
                    System.out.printf("%d+", a[i]);
                if (s == 0)
                    System.out.printf("%d", a[i]);
            }

        }
        System.out.println("\n");
    }

    public static void search(int t, int[] a, int n, int[] visit, String[] sta, int m) {
        for (int i = m; i < a.length; i++) {
            if (visit[i] == 0) {
                visit[i] = 1;
                a[t] = i;
                if (t == n) {
                    print(sta, a);
                } else
                    search(t + 1, a, n, visit, sta, i + 1);
                visit[i] = 0;

            }
        }
    }

    public static void print(String[] st, int[] a) {
        for (int j = 0; j < a.length; j++) {
            if (a[j] != -1)
                System.out.printf("%s  ", st[a[j]]);

        }
        System.out.println("\n");
    }

    public static void getisempty(int[][] matrix, int[][][] visit) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] != 0) {
                    visit[i][j][0] = 10;
                } else {
                    for (int m = 0; m < matrix.length; m++) {
                        if (matrix[i][m] != 0) {
                            visit[i][j][matrix[i][m]] = 1;
                        }
                        if (matrix[m][j] != 0) {
                            visit[i][j][matrix[m][j]] = 1;
                        }
                    }
                    int i1 = i / 3;
                    int j2 = j / 3;
                    for (int m1 = i1 * 3; m1 < i1 * 3 + 3; m1++) {
                        for (int n1 = j2 * 3; n1 < j2 * 3 + 3; n1++) {
                            if (matrix[m1][n1] != 0) {
                                visit[i][j][matrix[m1][n1]] = 1;
                            }
                        }
                    }
                }
            }
        }
    }

    public static int canadd(int[] a) {
        int sum = 0;
        int time = 0;
        for (int i = 1; i < a.length; i++) {
            if (a[i] != 0) {
                sum++;
            } else
                time = i;
        }
        if (sum == 8) {
            return time;
        } else {
            return -1;
        }
    }

    public static int dd(int[] a) {
        int sum = 0;
        for (int i = 1; i < a.length; i++) {
            if (a[i] == 0) {
                sum++;
            }
        }
        return sum;
    }

    public static void addnumber(int[][] matrix, int[][][] visit) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {

                if (canadd(visit[i][j]) != -1) {
                    matrix[i][j] = canadd(visit[i][j]);
                    visit[i][j][0] = 10;
                } else {
                    visit[i][j][0] = dd(visit[i][j]);
                }

            }
        }
    }

    public static void back(int[][] matrix, int[][][] visit) {
        if (!isok(matrix)) {
            for (int mw = 2; mw < 9; mw++) {
                int[][] a = nextone(visit, mw);
                int[][] matrix1 = new int[9][9];
                for (int i = 0; i < 9; i++) {
                    for (int j = 0; j < 9; j++)
                        matrix1[i][j] = matrix[i][j];
                }
                int[][][] visit1 = new int[9][9][10];
                for (int i = 0; i < 9; i++) {
                    for (int j = 0; j < 9; j++)
                        for (int m = 0; m < 10; m++)
                            visit1[i][j][m] = visit[i][j][m];
                }

                if (a != null)
                    for (int i = 0; i < mw; i++) {
                        visit[a[i][0]][a[i][1]][a[i][2]] = 1;
                        addnumber(matrix, visit);
                        getisempty(matrix, visit);
                        back(matrix, visit);
                        if (!isok(matrix)) {
                            for (int i1 = 0; i1 < 9; i1++) {
                                for (int j1 = 0; j1 < 9; j1++)
                                    matrix[i1][j1] = matrix1[i1][j1];
                            }
                            for (int i1 = 0; i1 < 9; i1++) {
                                for (int j1 = 0; j1 < 9; j1++)
                                    for (int m = 0; m < 10; m++)
                                        visit[i1][j1][m] = visit1[i1][j1][m];
                            }
                        }
                    }
            }
        }
    }

    public static int[][] nextone(int[][][] visit, int n) {
        int[][] a = new int[n][3];
        int k = 0;
        int sum = 0;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (visit[i][j][0] == n) {
                    sum++;
                    for (int m = 1; m < 10; m++) {
                        if (visit[i][j][m] == 0) {
                            a[k][0] = i;
                            a[k][1] = j;
                            a[k][2] = m;
                            k++;
                        }
                    }
                    return a;
                }
            }
        }
        return null;
    }

    public static boolean isok(int[][] matrix) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (matrix[i][j] == 0) {
                    return false;
                }
            }
        }
        return true;
    }
}